package chapter04_RecursionAndDynamic;

import java.util.HashMap;
import java.util.Map;
import java.util.function.IntPredicate;

/**
 * 描述：数组中的最长连续序列
 *
 * @author hl
 * @date 2021/7/25 10:56
 */
public class LongestConsecutive {
    public static void main(String[] args) {
        int[] arr = {100,3,200,2,1,4};
        LongestConsecutive main = new LongestConsecutive();
        int count = main.longestConecutive(arr);
        System.out.println(count);
    }
    public int longestConecutive(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                //之前已经处理过这个数了，直接跳过
                continue;
            }
            map.put(arr[i], 1);
            //如果这个数没出现过
            if (map.containsKey(arr[i] - 1)) {
                res = Math.max(res, merge(map, arr[i] - 1, arr[i]));
            }
            if(map.containsKey(arr[i] + 1)){
                res = Math.max(res, merge(map, arr[i], arr[i] + 1));
            }
        }
        return res;
    }
    //合并两个范围，只需要更新范围的最小值和最大值，中间的值没有意义
    private int merge(Map<Integer, Integer> map, int less, int more) {
        int left = less - map.get(less) + 1;
        int right = more + map.get(more) - 1;
        int len = right - left + 1;
        map.put(left, len);
        map.put(right, len);
        return len;
    }
}
